//算法思路：
// 将链表通过暴力合并到链表1中
// 时间复杂度较低，但算法复杂，且空间复杂度高，不建议使用
public class Solution_1 {
    public ListNode mergeTwoLists(ListNode list1head, ListNode list2head) {
        if (list1head == null) {
            return list2head;
        }
        if (list2head == null) {
            return list1head;
        }
        ListNode a = list1head;
        ListNode b = list2head;
        ListNode preA = null;
        do{

            if (a.val <= b.val) {
                preA = a;
                a = a.next;
                if(a==null)
                {
                    preA.next = b;
                    do
                    {
                        b = b.next;
                    }while (b!=null);
                }
            } else {
                if (preA == null) {
                    preA=new ListNode();
                    preA.val = b.val;
                    preA.next = a;
                    list1head=preA;
                    b=b.next;
                } else {
                    ListNode insert = new ListNode();
                    insert.val=b.val;
                    insert.next = a;
                    preA.next = insert;
                    preA=insert;
                    if(b!=null)
                    {
                        b = b.next;
                    }
                    else {
                        return list1head;
                    }
                }
            }
        }while (a!=null&&b!=null);

        return list1head;
    }
}
